class Solution(object):
    def numSubarraysWithSum(self, nums, goal):
        prefix_l = {}
        prefix_r = {}
        n = len(nums)
        prefix_l[0] = -1
        prefix_r[0] = -1
        count = 0
        c = 0
        for i in range(n):
            count += nums[i]
            if count - goal in prefix_l:
                c += prefix_r[count - goal] - prefix_l[count - goal] + 1
            if count not in prefix_l:
                prefix_l[count] = i
            prefix_r[count] = i
        return c

data = Solution()
nums = [1,0,1,0,1]
goal = 2
print(data.numSubarraysWithSum(nums, goal))
